package newcoder.t7;

//[1,-2,3,10,-4,7,2,-5]
public class Solution {

    public static void main(String[] args) {
        int[] a = {1, -2, 3, 10, -4, 7, 2, -5};
        int[] ints = FindGreatestSumOfSubArray(a);
        for (int anInt : ints) {
            System.out.print(anInt+",");
        }
    }

    public static int[] FindGreatestSumOfSubArray(int[] array) {
        // write code here
        int max = array[0];
        int result = max;
        int start = 0, end = 0;
        for (int i = 1; i < array.length; i++) {
            if (max < 0 && max < array[i]) {
                max = array[i];
                start = i;
                end = i;
            } else {
                max = max + array[i];
                if (max >= result) {
                    result = max;
                    end = i;
                }
            }
        }
        int length = end-start+1;
        int[] data = new int[length];
        for (int i = 0; i < length; i++) {
            data[i] = array[start+i];
        }
        return data;
    }
}
